
/**********************单向循环链表*******************/

/**
 * 链表节点
 */
class Node {
    constructor(content, next) {
        this.content = content;
        this.next = next;
    }
}

/**
 * 链表
 */
class LinkedList {
    constructor() {
        this.size = 0;
        this.head = null;
    }

    /**
     * 校验索引的合法性
     * @param {索引} index 
     */
    valid(index) {
        if (index < 0 || index > this.size) {
            throw new Error("out of index");
        }
    }
    /**
     * 获得指定索引位置的元素
     * @param {索引} index 
     */
    _node(index) {
        this.valid(index);
        let current = this.head;
        //不断循环遍历找到下一个节点
        for (let i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }

    /**
     * 增加元素add（）：尾部增加以及指定索引位置添加
     * 修改元素set（index，element）：修改指定索引位置的元素
     * 查找元素get（index）：获取指定位置的元素
     * 删除元素remove（index）：删除指定索引的元素
     * 清空链表clear（）；清空链表，删除所有元素
     */

    /**
     * 在指定位置新增节点
     * @param {元素内容} element 
     * @param {索引位置} index 
     */
    add(element, index) {
        //兼容只传一个的情况
        index = !!index ? index : this.size;
        this.valid(index);
        if (index == 0) {
            // 拿到原来的head
            let head = this.head;
            //防止之前是有头节点的，所以这里传head而不是null
            let newHead = new Node(element, head);
            let last = this.size <= 0 ? newHead : this._node(this.size - 1);
            this.head = newHead;
            last.next = newHead;
        } else {
            //让上一个节点的next指向新节点，新节点的next指向原节点
            // 拿到上一个节点
            let preNode = this._node(index - 1);
            preNode.next = new Node(element, preNode.next);
        }
        this.size++;
    }

    /**
     * 更新指定位置的元素
     * 直接将原节点的内容替换就好
     * @param {索引} index 
     * @param {元素内容} element 
     */
    set(index, element) {
        this.valid(index);
        let target = this._node(index);
        target.element = element;
        return target;
    }

    /**
     * 获取指定位置的节点信息
     * @param {索引信息} index 
     */
    get(index) {
        this.valid(index);
        return this._node(index);
    }

    /**
     * 删除指定索引位置的节点
     * 前一位置的next指向当前位置的next就好
     * @param {索引位置} index 
     */
    remove(index) {
        this.valid(index);
        if(index == 0){
            // 当只有一个节点的时候，这样是删不掉的
            // 所以特殊处理
            if(this.size ===1){
                this.head = null;
            }
            this.head = this.head.next;
            let last = this._node(this.size -1);
            last.next = this.head;
        }else{
            let preNode = this._node(index - 1);
            preNode.next = preNode.next.next;
        }
        this.size--;
    }

    /**
     * 清空链表
     */
    clear() {
        this.head = null;
        this.size = 0;
    }

    /**
     * 链表的反转
     */
    reverse() {
        /**
         * 反转链表
         * @param {头节点} head 
         */
        function reverseList(head) {
            if (head == null || head.next == null) return head;

            let newNode = null;

            while (!!head) {
                let temp = head.next;
                head.next = newNode;
                newNode = head;
                head = temp
            }
            return newNode;
        }

        this.head = reverseList(this.head);
        return this.head;
    }
}


let ll = new LinkedList();
ll.add(4);
ll.add(5);
ll.add(6, 1);
console.log('ll', ll);
ll.remove(0);
console.log('ll', ll.get(1));